Abstract:

To improve the efficiency and reduce rekeying cost of batch rekeying, marking based batch rekeying

 (MBBR) algorithm is proposed. Based on MBBR algorithm, one-way hash function and exclusive 

operation are used to compute new keys, and improved tree-based batch rekeying (ITBR) algorithm

 is presented. New keys of all renewed nodes in the tree are computed firstly, and then all 

rekeying messages are sent, which avoids the problem of out-of-sync between keys and data. 

Server's rekeying cost is analyzed theoretically, and accurate computation models of rekeying 

cost are established. Analysis shows the security of ITBR algorithm is strong, and simulation 

results show that its average rekeying cost is 45.6% of MBBR algorithm's cost. So the rekeying 

efficiency and communication performance is improved significantly when this algorithm 

is applied. 

Key words: key tree, one-way hash function, batch rekeying, rekeying cost